package Test;

import java.util.LinkedList;
import java.util.Queue;

public class T1 {
    public static void main(String[] args) {
        System.out.println(new T1().solution(new String[]{"X.....>", "..v..X.", ".>..X..", "A......"}));

    }
    public boolean solution(String[] B) {
        // Implement your solution here
        int n = B.length, m = B[0].length();
        char[][] grid = new char[n][m];
        for(int i = 0; i < n; i++){
            grid[i] = B[i].toCharArray();
        }

        boolean[][] danger = new boolean[n][m];
        int[][] dirs = {{0,-1},{0,1},{-1,0},{1,0}};
        char[] dirChars = {'<', '>', '^', 'v'};
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                char c = grid[i][j];
                for(int d = 0;d < 4; d++){
                    if(c == dirChars[d]){
                        int x = i, y = j;
                        while(true){
                            x += dirs[d][0];
                            y += dirs[d][1];
                            if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 'X') break;
                            if(grid[x][y] == '.' || grid[x][y] == 'A'){
                                danger[x][y] = true;
                            }
                        }
                    }
                }
            }
        }

        //TODO 找刺客起点
        int sx = -1, sy = -1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m;j++){
                if(grid[i][j] == 'A'){
                    sx = i;sy = j;
                }
            }
        }
        //TODO 搜索合适路径
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sx,sy});
        visited[sx][sy] = true;
        int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            if(x == n-1 && y == m - 1) return true;
            for(int[] mv : move){
                int nx = x + mv[0], ny = y + mv[1];
                if(nx>=0 && nx < n && ny >=0 && ny < m && !visited[nx][ny]){
                    if(grid[nx][ny] == '.' || (nx == n - 1 && ny == m - 1)){
                        if(!danger[nx][ny]){
                            visited[nx][ny] = true;
                            q.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
        return false;
    }
}
